# 42. 接雨水
# 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

# 动态规划，
# 时间复杂度：O(n)，计算left_max，right_max数组，统计，遍历了3遍数组。
# 空间复杂度：O(n)，left_max，right_max数组。
def trap_dp(height):
    """
    :type height: List[int]
    :rtype: int
    """
    height_len = len(height)
    # left_max 和 right_max 分别存储 i 的左边界最大值和右边界最大值
    left_max = [0] * height_len
    right_max = [0] * height_len

    for i in range(1, height_len):
        left_max[i] = max(left_max[i - 1], height[i - 1])

    for i in range(height_len - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i + 1])

    result = 0
    for i in range(1, height_len - 1):
        result += max(min(left_max[i], right_max[i]) - height[i], 0)
    # print(f"height:{height} , left_max:{left_max} , right_max:{right_max}")
    return result


# 单调栈
# 时间复杂度：O(n)，只需要遍历1遍数组。
# 空间复杂度：O(n)，只需要一个额外的栈，空间不超过n。
def trap_stack(height):
    """
    :type height: List[int]
    :rtype: int
    """
    # 创建一个单调递减栈，如何保证是单调递减的栈？
    stack = []
    result = 0
    height_len = len(height)
    for h_index in range(height_len):
        # 栈不为空，并且需要入栈的元素大于栈顶元素
        while stack and height[h_index] > height[stack[-1]]:
            # 取出栈顶元素下标
            top = stack.pop()
            if not stack:
                break
            left = stack[-1]
            # 求宽和高，并进行累加
            curr_width = h_index - left - 1
            curr_height = min(height[left], height[h_index]) - height[top]
            result += curr_width * curr_height
        # 开始往栈中存放元素的下标
        stack.append(h_index)

    print(f"stack:{stack}")
    return result


# 双指针
# 时间复杂度：O(n)
# 空间复杂度：O(1)
def trap_double_pointer(height):
    """
    :type height: List[int]
    :rtype: int
    """
    ans = 0
    left, right = 0, len(height) - 1
    # 使用一个临时变量，来替代动态规划当中的数组
    left_max = right_max = 0

    while left < right:
        # 及时更新临时变量的值
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])

        # 左边指针高度 < 右边指针高度，左边指针右移
        # 左边指针高度 >= 右边指针高度，右边指针左移
        if height[left] < height[right]:
            ans += left_max - height[left]
            left += 1
        else:
            ans += right_max - height[right]
            right -= 1

    return ans


height_1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
result = trap_stack(height_1)
print(f"result:{result}")

height_2 = [4, 2, 0, 3, 2, 5]
result = trap_stack(height_2)
print(f"result:{result}")

height_3 = [0, 1, 2, 3, 4, 5]
result = trap_stack(height_3)
print(f"result:{result}")
